package Solution101_200.problem113.PathSumII;

import common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @program Leetcode
 * @description:
 * @author: lishangsheng
 * @create: 2019/07/15 12:06
 */
public class BetterSolution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> ans = new ArrayList();
        helper(root, ans, new ArrayList(), sum);
        return ans;
    }

    private void helper(TreeNode root, List<List<Integer>> ans, List<Integer> curr, int sum)
    {
        if (root == null)
            return;
        curr.add(root.val);
        if (root.left == null && root.right == null && sum == root.val)
        {
            ans.add(new ArrayList<>(curr));
        }
        sum -= root.val;
        helper(root.left, ans, curr, sum);
        helper(root.right, ans, curr, sum);
        curr.remove(curr.size()-1);
        sum += root.val;
    }
}
